////////////////////////////////////////////////////////////////////////////////
// Auteur	: Maxime Vanier et Patrick Losier
// date		: 04/03/2013
//
// description : Implementation de l'algorithme Dynamique
///////////////////////////////////////////////////////////////////////////////

#include "Algorithmes.h"
#include "BTS.h"
#include "Timer.h"

#define MAX(a,b) (a > b)? a : b

const std::string AlgoDynamique::ID_DYNAMIQUE = "algo_dynamique";



AlgoDynamique::AlgoDynamique()
	: Algo(ID_DYNAMIQUE)
{
}

AlgoDynamique::~AlgoDynamique()
{
}

int AlgoDynamique::execute(const std::map<int,BTS*>& vBTS, int capacite, std::vector<int>& result)
{
	int* matrice[2];
	matrice[0] = new int[capacite];
	matrice[1] = new int[capacite];

	valeurMax_ = 0;

	for(int y = 0; y < capacite; y++)
	{
		matrice[0][y] = 0;
		matrice[1][y] = 0;
	}

	Timer timer;
	timer.start();

	for(int i = 0 ; i < vBTS.size() ; i++)
	{
		std::map<int,BTS*>::const_iterator itBTS = vBTS.find(i+1);
		if (itBTS == vBTS.end())
		{
			continue;
		}

		int revenu = itBTS->second->getRevenu();
		int abonne = itBTS->second->getNbAbonnes();

		for(int j = 0 ; j < capacite ; j++)
		{
			int matriceA = 0;
			if(j-abonne >= 0)
			{
				matriceA = matrice[i%2][j-abonne];
			}
			int matriceB = matrice[i%2][j];

			int revenuA = (j+1 >= abonne) ? revenu : 0; 

			int maxRet = MAX( revenuA + matriceA , matriceB );
			matrice[(i+1)%2][j] = maxRet;

			timer.stop();
			if (timer.getElapsedTimeInMilliSec() > timeout_)
			{
				return -1;
			}
		}
	}

	result.clear();
	valeurMax_ = MAX(matrice[0][capacite-1],matrice[1][capacite-1]);
	
	delete matrice[0];
	delete matrice[1];

	return 0;
}